package ds.tree.binaryTree
{
	import ds.tree.TreeNode;
	
	public class BinarySearchTree extends BinaryTree
	{
		public function BinarySearchTree()
		{
			super();
		}
		
		public function insert(data:Number,baseNode:BinaryTreeNode):void
		{
			if( baseNode == null )
				return;
			
			var compareResult:int = baseNode.compare( data );
			
			if( compareResult  == 1)
			{
				if( baseNode.rightNode )
				{
					insert(data,baseNode.rightNode);
				}
				else
					baseNode.rightNode = new BinaryTreeNode( baseNode,data);
			}
			else if( compareResult == -1)
			{
				if( baseNode.leftNode )
				{
					insert(data,baseNode.leftNode);
				}
				else
					baseNode.leftNode = new BinaryTreeNode( baseNode,data);
			}
		}
		
		public function remove( data:Number,baseNode:BinaryTreeNode ):void
		{
			if( baseNode == null )
				return;
			
			var removeNode:BinaryTreeNode = findNode( data,baseNode );
			
			if( removeNode == null )
				return;
			
			var node:BinaryTreeNode;
			
			if( removeNode.leftNode )
			{
				node = findMax( removeNode.leftNode );
			}
			else if( removeNode.rightNode )
			{
				node = findMin( removeNode.rightNode );
			}
			
			if(!node )
			{
				if( removeNode.parentNode)
				{
					removeNode.disconnect( removeNode.parentNode );
				}
			}
			else
			{
				if(node.parentNode)
				{
					node.disconnect( node.parentNode );
					
					node.parentNode = removeNode.parentNode;
					
					node.transferChildrenFrom( removeNode );
					
					if( node.parentNode )
						this._root = node;
				}
			}
		}
		
		public function contains( node:BinaryTreeNode,baseNode:BinaryTreeNode ):Boolean
		{
			if( !baseNode )
				return false;
			
			if( node == baseNode )
				return true;
			
			var parentNode:TreeNode = node.parentNode;
			
			while( parentNode )
			{
				if(parentNode == baseNode )
					return true;
				
				parentNode = node.parentNode;
			}
			
			return false;
		}
		
		public function findNode( data:Number,baseNode:BinaryTreeNode ):BinaryTreeNode
		{
			if( baseNode == null )
				return null;
			
			var compareResult:int = baseNode.compare( data );
			if(compareResult == 0 )
				return baseNode;
			else if ( compareResult == 1 )
				return findNode(data,baseNode.leftNode);
			else if (compareResult == -1)
				return findNode(data,baseNode.rightNode );
			
			return null;
		}
		
		public function findMin( baseNode:BinaryTreeNode ):BinaryTreeNode
		{
			if( baseNode == null )
				return null;
			
			if( baseNode.leftNode == null )
				return baseNode;
			
			return findMin( baseNode.leftNode );
		}
		
		public function findMax( baseNode:BinaryTreeNode ):BinaryTreeNode
		{
			if( baseNode == null )
				return null;
			
			if( baseNode.rightNode == null )
				return baseNode;
			
			return findMax( baseNode.rightNode );
		}
	}
}